Batch 3 - Class 105 - Jumping Frogs (Patterns, Induction)
Pre-Class Problem:
Find four different fractions, in each of which the numerator is one less than the denominator, so that when all four fractions are added together, their sum will be a whole number. There is more than one solution.
- Answer:1/2, 2/3, 6/7, 41/42 - Many other solutions
- Since each number is of form (n-1)/n which is 1-1/n, and since sum of all four is integer, it means that 1/a+1/b+1/c+1/d is an integer. The largest value of this is for a,b,c,d=2,3,4,5 which is 1.28, so the integer sum must be 1, and a must be 2. Hence 1/b+1/c+1/d=1/2. Now set b = 3 to find some solutions for c and d; then set b = 4 to find other solutions, and so on.
Attendance: Smiti, Muskaan, Khushi, Arnav, Anishka, Ahana, Arnav, Anisha, Liza, Zorawar, Diya, Nandini, Aneyaa, Arushi, Abhiram, Anshi, Manya
Class Notes:
This is a game that frogs play when humans are not seeing them. There are several lily pads in a straight line and a frog on each of them. However they want to have a party on the same lily pad.
 files\Untitled.png)
The rules are that one frog can jump one space, two frogs together can jump two and so on. All frogs on a lily pad must jump together, and they can't jump onto an empty lily pad.
- Start with five frogs and see if you can figure out how to get them to party together
- The next day, a new frog comes to town. Can they still party on the same lily pad?
- Can you think of this problem in terms of two smaller problems - can you reduce it to two frogs on two lily pads?
- Can you use your solution to now solve for 36 frogs?
- Can you use your approach to solve for 9 frogs?
- Can this approach be used for all numbers? How about prime numbers?
- If you can solve for 5, can you use that to solve for 6?
- If you can solve for 6, can you solve for 7?
- Instructor Note: Diversion to Induction - Introduce induction to kids. Try and establish the condition, which if it holds, allows us to add another frog and solve for that
- Note that it is enough to be able to solve with N frogs, and be able to land up at either corner, to then be able to solve for N+1
- What does this imply in terms of solving for any number?
- Instructor Note: Articulate the base and induction step for an induction argument
Now we have a queen frog. She likes to remain on top of any stack.
- Can we solve this problem with the queen's wishes?
- What positions does the queen need to be to afford a solution?
- Can it be solved for any position of the queen?
- Can you think of this problem in terms of the generic solution for N?
What if we have a lazy frog - one who would never jump?
- Can we solve with a lazy frog? At what positions?
- What does this problem translate into?
- (The party must be held on the lazy frog's home. Note that since frogs can't jump onto the lazy frog, rest everyone must come there)
- Can you think of this problem in terms of generic solution for N?
Homework
- What if you had one queen frog and one lazy frog? Is it always possible? If not, when?
- What if there are some lily pads that are waterlogged - i.e. no frogs can get there? Can this be solved? [Open problem]
References: